package leetcode.code0127;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;
import java.util.Set;

//【瓦片】127. 单词接龙 Java 78.69% 宽度优先搜索
public class Solution extends Solution127 {

	Map<String, List<String>> ways;// 所有联通路径<原词,通配词列表> <通配词,原词列表>

	@Override
	public int ladderLength(String beginWord, String endWord, List<String> wordList) {
		if (!wordList.contains(endWord)) {// 没有endWord，肯定没戏唱
			return 0;
		}
		if (!wordList.contains(beginWord)) {
			wordList.add(beginWord);// 为了做路用,wordList初始化ways时，捎带脚给beginWord也做了。
		}
		ways = new HashMap<>();// 所有联通路径<原词,通配词列表> <通配词,原词列表>
		this.findWays(wordList);// 初始化ways
		Set<String> done = new HashSet<>();// 走过的路
		Queue<String> q = new LinkedList<>();// 宽优搜索队
		q.add(beginWord);// 起始点
		int ans = 0;// 答案
		while (!q.isEmpty()) {
			int size = q.size();// 当前层宽度
			ans += 1;// 途径词数+1，每经历一层，层数+1
			while (size > 0) {// 宽搜这一层
				String from = q.poll();
				if (from.equals(endWord)) {// 找到endWord返回
					return ans;
				}
				this.move(q, done, from);// from词步入下一层
				size--;// 当前层数量-1
			}
		}
		return 0;
	}

	private void move(Queue<String> q, Set<String> done, String from) {
		List<String> links = ways.get(from);// 每个from原词，通过link通配词，连接到to原词上
		for (String link : links) {
			List<String> tos = ways.get(link);// 从原词from到原词to
			for (String to : tos) {
				if (!done.contains(to)) {// 不能是走过的
					done.add(to);// 没走过的变成走过
					q.add(to);// 添加到宽优队中
				}
			}
		}
	}

	// 初始化路ways变量
	private void findWays(List<String> wordList) {
		for (String from : wordList) {
			char[] cur = from.toCharArray();
			for (int i = 0; i < cur.length; i++) {// 原词的每一位变成通配词
				char c = cur[i];
				cur[i] = '*';// 变更i位
				this.add2ways(from, new String(cur));// 建立原词和通配词的路
				cur[i] = c;// 回溯
			}
		}
	}

	// 建立<原词,通配词列表> <通配词,原词列表>
	private void add2ways(String from, String link) {
		List<String> list = ways.getOrDefault(from, new ArrayList<>());
		list.add(link);
		ways.put(from, list);// 原词列表中添加一个通配词
		list = ways.getOrDefault(link, new ArrayList<>());
		list.add(from);
		ways.put(link, list);// 通配词列表中添加一个原词
	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug1();
		so.debug2();
		so.debug5();
		so.debug3();

	}

}
